package haxe.util;

typedef SEntry = {
	var prev:SEntry;
	var value:Dynamic;
}

class Stack<T> implements Collection<T>
{
	public var size(getSize,null):Int;
	
	private var _s:Int;
	private var _top:SEntry;
	
	public function new()
	{
		this._s = 0;
		this._top = null;
	}
	
	public function add(o:T):Void
	{
		this.push(o);
	}
	
	public function addAll(c:Collection<T>):Void
	{
		for( i in c )
			this.add(i);
	}
	
	public function remove(o:T, ?equal:T->T->Bool ):Bool
	{
		if ( equal == null )
			return this.removeNatEq(o);
		else
			return this.removeFuncEq( o, equal );
	}
	
	public function removeAll(c:Collection<T>, ?equal:T->T->Bool ):Bool
	{
		var r:Bool = false;
		if ( equal == null )
		{
			for ( i in c )
			{
				if ( this.removeNatEq( i ) && !r )
					r = true;
			}
		}else{
			for ( i in c )
			{
				if ( removeFuncEq( i, equal ) && !r )
					r = true;
			}
		}
		return r;
	}
	
	public function contains(o:T, ?equal:T->T->Bool ):Bool
	{
		if( this._s == 0 )
			return false;
		var e:SEntry = this._top;
		if ( equal == null )
		{
			while( e.prev != null )
			{
				if( e.value == o )
					return true;
				e = e.prev;
			}
			return e.value == o;
		}else{
			while( e.prev != null )
			{
				if( equal(e.value, o ) )
					return true;
				e = e.prev;
			}
			return equal(e.value, o );
		}
	}
	
	public function containsAll( c:Collection<T>,  ?equal:T->T->Bool ):Bool
	{
		if( this._s < c.size )
			return false;
		for ( i in c )
		{
			if ( ! contains(i, equal) )
				return false;
		}
		return true;
	}
	
	public function push(o:T):Void
	{
		this._top = { prev:_top, value:o};
		++this._s;
	}
	
	public function pop():T
	{
		var r:T = this._top.value;
		this._top = this._top.prev;
		if( _s > 0 ) --_s;
		return r;
	}
	
	public function isEmpty():Bool
	{
		return this._s == 0;
	}
	
	public function clear():Void
	{
		this._top = null;
		this._s = 0;
	}
	
	public function iterator():Iterator<T>
	{
		return new StackIterator(this._top);
	}
	
	public function toArray():Array<T>
	{
		var _a:Array<T> = new Array();
		var it:SEntry = this._top;
		while( it != null )
		{
			_a.push(it.value);
			it = it.prev;
		}
		//_a.reverse();
		return _a;
	}
	
	public function getTop():T
	{
		return this._top.value;
	}
	
	private function removeNatEq(o:T):Bool
	{
		if ( _s > 1 )
		{
			if ( _top.value == o)
			{
				this._top = this._top.prev;
				--this._s;
				return true;
			}
			var e:SEntry = this._top;
			var n:SEntry;
			while ( e != null && e.value != o )
			{
				n = e;
				e = e.prev;
			}
			if ( e.value == o)
			{
				n.prev = e.prev;
				--_s;
				return true;
			}else
				return false;
		}
		else if ( this._s == 1 && this._top.value == o )
		{
			this._top = null;
			_s = 0;
			return true;
		}else
			return false;
	}
	
	private function removeFuncEq( o:T, eq:T->T->Bool ):Bool
	{
		if ( _s > 1 )
		{
			if ( eq(_top.value, o) )
			{
				_top = _top.prev;
				--_s;
				return true;
			}
			var e:SEntry = _top;
			var n:SEntry;
			while ( e != null && !eq(e.value, o) )
			{
				n = e;
				e = e.prev;
			}
			if ( eq(e.value, o) )
			{
				n.prev = e.prev;
				--_s;
				return true;
			}else
				return false;
		}
		else if ( _s == 1 && eq( _top.value, o ))
		{
			_top = null;
			_s = 0;
			return true;
		}else
			return false;
	}
	
	private function getSize():Int
	{
		return this._s;
	}
}

class StackIterator<T>
{
	private var _e:SEntry;
	
	public function new( top:SEntry )
	{
		_e = {prev:top,value:null};
	}
	public function hasNext() 
	{
		return _e.prev != null;
	}

	public function next():T
	{
		_e = _e.prev;
		return _e.value;
	}
}
